/*
 * com.future CO.,ltd.
 */
package com.future;

/**
 * Description:
 * 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * <p>
 * 假设你总是可以到达数组的最后一个位置。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [2,3,1,1,4]
 * 输出: 2
 * 解释: 跳到最后一个位置的最小跳跃数是 2。
 *      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author: future
 * @Date:2022/3/31:0:07
 */
public class Solution_45 {

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        nums = new int[]{3, 4, 1, 3, 2, 4, 2, 1};
        nums = new int[]{2, 3, 0, 1, 4};
        nums = new int[]{3, 4, 5, 2, 1, 6, 5, 4, 7, 3, 2, 0, 3};
        System.out.println(jump(nums));
    }

    /**
     * {3, 4, 5, 2, 1, 6, 5, 4, 7, 3, 2, 0, 3}
     * 思路：
     * 遍历时，以下三个值的变化情况
     * --------------------------------------------
     * ~~~~[3, 4, 5, 2, 1, 6, 5, 4, 7, 3, 2, 0, 3] |
     * ~~~~|0  1  2  3  4  5  6  7  8  9  10 11 12 |
     * -------------------------------------------
     * step|0  1  1  1  2  2  2  2  3  3  3  3  4  |
     * cur |0  3  3  3  7  7  7  7  11 11 11 11 15 |
     * next|3  5  7  7  7  11 11 11 15 15 15 15 15 |
     * step 到当前已经需要的步数
     * cur 遍历到当前坐标下最远能到达的右边坐标
     * next 到当前，下一步最远能到达的下标
     *
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int cur = 0;// 遍历到当前坐标下最远能到达的右边坐标
        int step = 0; // 到当前已经需要的步数
        int next = 0; // 到当前，下一步最远能到达的下标
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            if (i > cur) {
                step++;
                cur = next;
            }
            next = Math.max(next, i + nums[i]);
        }
        return step;
    }

}
